694. Задача Коллатса

Пусть имеется некоторое положительное целое число A. Будем производить с ним следующие действия:

Шаг 1. Если A = 1, то остановиться.

Шаг 2. Если A четное, то заменить A на A/2 и перейти к шагу 1.

Шаг 3. Если A нечетное, то заменить A на 3*A + 1 и перейти к шагу 1.

По заданному A необходимо подсчитать количество чисел, которое будет порождено алгоритмом до его остановки на шаге 1, либо сколько чисел будет порождено пока его текущее значение не превысит заданного лимита L.

Вход. Каждая строка содержит два числа A и L, не больших 2,147,483,647. Известно, что A < L. Признаком конца входных данных будут отрицательные значения A и L.

Выход. Для каждого теста вывести его номер, двоеточие, исходное значение A, лимит L и количество шагов вычисления до остановки или до достижения значения, превышающего L.

Пример входа

3 100
34 100
75 250
27 2147483647
101 304
101 303
-1 -1
 

Пример выхода

Case 1: A = 3, limit = 100, number of terms = 8
Case 2: A = 34, limit = 100, number of terms = 14
Case 3: A = 75, limit = 250, number of terms = 3
Case 4: A = 27, limit = 2147483647, number of terms = 112
Case 5: A = 101, limit = 304, number of terms = 26
Case 6: A = 101, limit = 303, number of terms = 1
 

РЕШЕНИЕ

элементарные вычисления

Анализ алгоритма

Запишем функцию f, которая по текущему значению A порождает следующее значение согласно описанному алгоритму. Задача решается простой генерацией последовательности, числа которой удовлетворяют заданным условиям.

Пример

При n = 3 в ходе вычислений получим последовательность из 8 чисел: 3, 10, 5, 16, 8, 4, 2, 1.

Реализация алгоритма

По условию задачи значения A и L не больше 2,147,483,647. Но в некоторый момент вычислений может появиться число, большее 2,147,483,647. Тогда оно станет большим заданного лимита и порождение последовательности завершится. Для простоты реализации алгоритма будем использовать 64-битовый целый тип long long (для GNU C). В Visual C используется тип __int64. Глобальные переменные имеют вид:

long long a, limit, res;

Функция f(n) вычисляет следующее после n значение согласно описанному в условии задачи алгоритма.

long long f(long long n)

{

if (n % 2) return 3 * n + 1;

return n / 2;

}

Начальное значение a запомним в переменной tempa. Производим вычисления функции f, пока текущее число не станет равным 1 или не станет большим limit. Количество вычислений f подсчитываем в переменной res. Результат выводим в соответствии с требуемым форматом.

while(scanf("%lld %lld",&a,&limit), a + limit > 0)

{

tempa = (int)a; res = 1;

while(a > 1)

{

a = f(a);

if (a > limit) break;

res++;

}

printf("Case %d: A = %d, limit = %lld, number of terms =

%lld\n",cs++,tempa,limit,res);

}